package 剑指专题.其他;


/*
 * Author：江松
 * Date：2023/4/4 9:37
 *
 孩子们的游戏:
 1,暴力模拟
 2,公式:
 定义问题，f(n,m)表示n个孩子报数m时，剩下的孩子编号
 考虑它如何由子问题转移而来：以前这个孩子（存活的）编号应该为m，移出一个孩子（m-1)后，
 这个孩子编号为0，相对于以前增加了m
 f(n,m)=(f(n-1,m)+m)%n
 */

public class Main12 {
    //迭代:子问题就是f(0,m)...f(n-1,m)，那么%n就相当于枚举（1~n）
    public int LastRemaining_Solution(int n, int m){
        int f=0;
        for(int i=1;i<=n;++i){
            f=(f+m)%i;
        }
        return f;
    }
    /*
    //递归写法
    public int LastRemaining_Solution(int n, int m) {
        if(n==1)return 0;
        return (LastRemaining_Solution(n-1,m)+m)%n;
    }
    */


    /*
    public int LastRemaining_Solution(int n, int m) {
        int cnt=0;
        int mm=0;
        //是否出列
        boolean vis[]=new boolean[n+1];
        int i;
        for(i=0;cnt<n-1;i=(i+1)%n){
            if(!vis[i]){
                if(mm++==m-1){
                    vis[i]=true;
                    cnt++;
                    mm=0;
                }
            }
        }
        for(i=0;i<n;++i){
            if(!vis[i])return i;
        }
        return -1;
    }
    */
}
